【题解】 [九省联考2018]林克卡特树 树形DP+wqs二分优化 loj2478 | Qiuly's blog!

【题解】 [九省联考2018]林克卡特树 树形DP+wqs二分优化 loj2478

Posted on | In | Comments:

毒瘤传送门：戳我戳我

仔细观察会发现该题需要从树上拿出 $k+1$ 条互不相交的链，求这些链的节点的权值总和的最大值。那么我们选出这些链后就可以用 $k$ 条边将其连起来了，这样就满足了题意。

用 $f_{i,j}$ 表示 $i$ 的子树中选出了 $j$ 个链的最大值，但是会发现转移很难办，枚举一个 $i$ 的儿子 $v$ 的时候，我们不好算出 $v$ 对 $i$ 上的链做出的贡献。

那么我们新增加一个状态，设 $f_{0/1/2,i,j}$ 为我们的状态，$i,j$ 的意思和上面一样，其中 $0/1/2$ 分别表示——$0$ : $i$ 不属于子树中 $j$ 条链中的任意一条，$1$ : $i$ 属于 $j$ 条链中其中一条，$2$ : $i$ 属于 $j$ 条链中的其中两条 。

那么我们枚举一个儿子 $v$ ，现在我们需要转移的对象就是 $u$ (上面的 $i$ ) ，那么我们注意来考虑：

我们转移的时候枚举一个 $i$ 表示当前的链数，然后枚举 $j$ 表示 $v$ 子树中的链数，那么之前 $u$ 子树中的链数显然就是 $i-j$ 了。

令 $num_{v,j}=\max(f_{0,v,j},f_{1,v,j},f_{2,v,j})$ .

  • 计算 $v$ 对 $f_{0,u,i}$ 的贡献

    • 因为该状态必须满足 $u$ 不能属于任意一条链，所有我们理所当然也不能连上 $u\rightarrow v$ 这条边。那么也就是说 $v$ 中发生什么事情都跟 $u$ 没有任何关系了，因为要统计最大，我们直接将 $num$ 统计进去即可。

    • 转移：

  • 计算 $v$ 对 $f_{1,u,i}$ 的贡献

    • 考虑两种情况，第一种，这一条和 $u$ 有关的链是连着别的子树的，那么也就肯定不会连上 $u\rightarrow v$ 这条边，按照上面的转移即可。

    • 第一种转移：

    • 第二种情况就是这一条链是和 $v$ 相连接的，那么这个时候 $v$ 的状态只能是 $0,1$ ，原因很显然，链不能香蕉(最好吃了🍌) ，那么对于 $v$ 状态是 $0$ 的情况，这样一连接后就会新出现一条链了，记得算上边权：

    • 转移 $0$ 情况：

      $f_{0,u,i-j}$ 不解释，$f_{0,v,j-1}$ 这里为什么要 $j-1$ 呢？因为很显然当前局面只有 $i-1$ 条链，上面讲了连接后会多出来一条，那么 $i-1+1$ 就正好用来转移 $i$ 了。最后的 $w$ 即为当前转移带来的贡献。

    • $v$ 的状态是 $1$ 的时候和上面差不多，但是因为连接 $u,v$ 后 $u$ 属于了原来就存在的一条链，也就是说没有新增链，那么就没必要 $j-1$ 了。

    • 转移 $1$ 的情况：

  • 计算 $v$ 对 $f_{2,u,i}$ 的贡献

    • 首先如果这两条链连接别的子树了，那么 $v$ 就没有限制了，转移同上：

    • 转移：

    • 接下来的就很好办了，因为连接 $u,v$ 最多是一条链，也就是说我们不可能将两条链都放到 $v$ 下来。先考虑 $v$ 状态为 $0$ 的情况，因为连接后 $v$ 属于了 $u$ 原来所在的链(没有新增链)，那么直接算贡献：

    • 转移：

    • 然后考虑 $v$ 状态为 $1$ 的情况，这个时候连接 $u,v$ 会使得 $v$ 原来所在的链和 $u$ 原来所在的链合并为一条链，那么这里的和上面的 $j-1$ 不同，这里因为是少了一条链所有要变成 $j+1$ 。

    • 转移：

所有的转移式都得到了，我们来考虑初始化，首先因为是取最大值，我们需要全部初始化为一个很小的负数。然后对于 $f_{0,u,0}$ 这样的状态的值很显然是 $0$ 。

其他的没了，注意这样的 $\rm{DP}$ 复杂度只能让我们最多拿到 $60$ 分。

Code (60 $pts$ ) ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=3e5+2;
const int inf=1e9+9;

int n,k,sz[N],head[N],cnt;
ll dp[3][N][110];
struct Edge{int nxt,to,val;} G[N<<1];
void add(int u,int v,int w) {
    G[++cnt]=(Edge){head[u],v,w},head[u]=cnt;
    G[++cnt]=(Edge){head[v],u,w},head[v]=cnt;
}

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

void dfs(int u,int fa) {
    dp[0][u][0]=0;/*初始化*/
    for(int e=head[u];e;e=G[e].nxt) {
        int v=G[e].to,w=G[e].val;
        if(v==fa) continue;
        dfs(v,u),sz[u]+=sz[v];
        /*利用sz数组优化，同样是O(nk^2)的代码，其他的只能拿到30
        ~40，但是这个优化过后是妥妥的60分*/
        for(int i=min(sz[u],k);i;--i) {
            /*计算v下面没有链的情况，计算初始状态带来的贡献*/
            dp[2][u][i]=max(dp[2][u][i],dp[1][u][i]+w);
            dp[2][u][i]=max(dp[2][u][i],dp[1][u][i]+dp[1][v][1]+w);
            for(int j=min(sz[v],i);j;--j) {
                /*计算出num*/
                ll num=max(dp[0][v][j],max(dp[1][v][j],dp[2][v][j]));
                /*下面的7个式子就是上文讲的转移了*/
                dp[0][u][i]=max(dp[0][u][i],dp[0][u][i-j]+num);

                dp[1][u][i]=max(dp[1][u][i],dp[1][u][i-j]+num);
                dp[1][u][i]=max(dp[1][u][i],dp[0][u][i-j]+dp[1][v][j]+w);
                dp[1][u][i]=max(dp[1][u][i],dp[0][u][i-j]+dp[0][v][j-1]+w);

                dp[2][u][i]=max(dp[2][u][i],dp[2][u][i-j]+num);
                dp[2][u][i]=max(dp[2][u][i],dp[1][u][i-j]+dp[0][v][j]+w);
                dp[2][u][i]=max(dp[2][u][i],dp[1][u][i-j]+dp[1][v][j+1]+w);
            }
            /*也是一种特殊情况，可以直接放到上面去的(v下没有链)*/
            dp[1][u][i]=max(dp[1][u][i],dp[0][u][i-1]+w);
        }
    }
    if(!sz[u]) dp[0][u][1]=0;
    ++sz[u];
}

int main() {
    IN(n),IN(k);
    for(int i=1;i<n;++i) {
        int x,y,v;IN(x),IN(y),IN(v),add(x,y,v);
    }
    memset(dp,-0x3f,sizeof(dp));/*极小值*/
    ++k;dfs(1,0);
    printf("%lld\n",max(dp[0][1][k],max(dp[1][1][k],dp[2][1][k])));
    /*输出最优👆*/
    return 0;
}

如果打出了表，你会发现对于单调递增的 $k$ ，关于其的最优解所形成的一定是一个上凸的函数，感性理解的话就是说 $k$ 小的时候我们可以选更多的更大的边，但是随着 $k$ 增大，这些边不够了，我们只能选更小的或者是拆掉一些边(将一条链断成两条增加链数) ，这样子答案就好慢慢变小。

因为是上凸函数，我们可以使用 $\rm{DP}$ 凸优化，带权二分/$wqs$二分套路优化一下就可以过了。

注意二分边界！还有就是需要注意一个点也可以成为一条链的情况！

Code (100 $pts$ )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=6e5+2;
const ll inf=1e18+9;

int n,k,head[N],cnt;
struct date {
    ll x;int y;
    bool operator < (const date&var) const {return x==var.x?y>var.y:x<var.x;}
    date operator + (const date&var) {return (date){x+var.x,y+var.y};}
    date operator + (const ll&var) {return (date){x+var,y};}
}dp[3][N];
ll number(date var) {return var.x;}
struct Edge{int nxt,to,val;} G[N<<1];
void add(int u,int v,int w) {
    G[++cnt]=(Edge){head[u],v,w},head[u]=cnt;
    G[++cnt]=(Edge){head[v],u,w},head[v]=cnt;
}

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

void check(ll add,int u,int fa) {
    dp[0][u]=(date){0,0},
    dp[1][u]=(date){-inf,0},
    dp[2][u]=(date){add,1};
    for(int e=head[u];e;e=G[e].nxt) {
        int v=G[e].to;
        ll w=G[e].val;
        if(v==fa) continue;
        check(add,v,u);
        date num=max(dp[0][v],max(dp[1][v],dp[2][v]));

        dp[2][u]=max(dp[2][u],dp[2][u]+num);
        dp[2][u]=max(dp[2][u],dp[1][u]+(date){w,0}+max(dp[0][v],dp[1][v]+(date){-add,-1}));

        dp[1][u]=max(dp[1][u],dp[1][u]+num);
        dp[1][u]=max(dp[1][u],dp[0][u]+(date){w,0}+max(dp[1][v],dp[0][v]+(date){add,1}));

        dp[0][u]=dp[0][u]+num;
    }return;
}

ll wqs(ll sum) {
    ll l=-sum,r=sum,mid;
    date now;
    while(l<r) {
        mid=(l+r+1)>>1,check(mid,1,0);
        now=max(dp[0][1],max(dp[1][1],dp[2][1]));
        if(!(now.y^k)) {l=r=mid;break;}
        now.y<k?l=mid:r=mid-1;
    }
    mid=l;check(mid,1,0);
    now=max(dp[0][1],max(dp[1][1],dp[2][1]));
    return now.x-mid*k;
}

int main() {
    // freopen("lct2.in","r",stdin);
    // freopen("P4383.out","w",stdout);
    IN(n),IN(k);++k;
    ll sum=0;
    for(int i=1;i<n;++i) {
        int x,y,v;IN(x),IN(y),IN(v);
        add(x,y,v),sum+=abs(v);
    }
    printf("%lld\n",wqs(sum));
    return 0;
}

本文标题:【题解】 [九省联考2018]林克卡特树 树形DP+wqs二分优化 loj2478

文章作者:Qiuly

发布时间:2019年05月12日 - 00:00

最后更新:2019年05月12日 - 16:54

原始链接:http://qiulyblog.github.io/2019/05/12/[题解]loj2478/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。